/*************************************************************************
> File Name: bucket_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-22 11:33:07
> Description: 桶排序 --  值不等于0
************************************************************************/
#include <string.h>
#include <stdlib.h>
#include "general.h"
#include <stdio.h>
static int insertionsort(int *arr, int length);
void bucketSort(int arr[], int length);
int main(int argc, char const *argv[])
{
    int arr[10] = {9, 4, 2, 7, 5, 1, 8, 3, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    bucketSort(arr, size);
    printf("Sorted array: \n");
    printArr(arr, size);
}

void bucketSort(int arr[], int length)
{
    // 找到数组中的最大值和最小值
    int max = getArrMax(arr, length);
    int min = getArrMin(arr, length);
    // 计算桶的数量
    int bucketNum = (max - min) / length + 1;

    // 创建桶数组
    int **buckets = (int **)malloc(bucketNum * sizeof(int *));
    for (int i = 0; i < bucketNum; i++)
    {
        buckets[i] = (int *)malloc(length * sizeof(int));
        memset(buckets[i], 0, sizeof(buckets[i]));
    }

    // 将元素放入桶中
    for (int i = 0; i < length; i++)
    {
        int index = (arr[i] - min) / length;
        int j;
        for (j = 0; j < length; j++)
        {
            if (buckets[index][j] == 0)
            {
                buckets[index][j] = arr[i];
                break;
            }
        }
        // 如果桶已满，则进行扩容
        if (j == length)
        {
            int *temp = (int *)realloc(buckets[index], 2 * length * sizeof(int));
            if (temp == NULL)
            {
                printf("realloc error");
                return;
            }
            buckets[index] = temp;
            buckets[index][j] = arr[i];
        }
    }

    // 对每个桶中的元素进行排序
    for (int i = 0; i < bucketNum; i++)
    {
        int *bucket = buckets[i];
        int len = 0;
        for (int j = 0; j < length; j++)
        {
            if (bucket[j] != 0)
            {
                len++;
            }
        }
        insertionsort(bucket, len);
    }

    // 合并桶中的元素
    int index = 0;
    for (int i = 0; i < bucketNum; i++)
    {
        int *bucket = buckets[i];
        for (int j = 0; j < length; j++)
        {
            if (bucket[j] != 0)
            {
                arr[index++] = bucket[j];
            }
        }
    }

    // 释放桶数组的内存
    for (int i = 0; i < bucketNum; i++)
    {
        free(buckets[i]);
    }
    free(buckets);
}
static int insertionsort(int *arr, int length)
{
    int i = 0, j = 0;
    int key = 0;
    for (i = 1; i < length; i++) // 1.从第二个开始、第一个数总是有序的
    {
        // 初始化
        key = *(arr + i);
        j = i - 1; // 从i-1开始判断是否移位
        // 调整位置
        while (j >= 0 && *(arr + j) > key) // 2.移动所有比他大的数，直到遇见一个小于等于他得数
        {
            *(arr + j + 1) = *(arr + j); // 3.移动的(  j+1 =j  截止在j)
            j--;
        }
        // 赋值    将他放在j+1的位置
        *(arr + j + 1) = key; // 4.由于前j个元素有序
    }
}